# Q: Given a sequence of integers, both positive and negative, find the
# contiguous subsequence with the maximum sum. For instance, given the sequence
# 31, -41, 59, 26, -53, 58, 97, -93, -23, 84, the maximum sum subsequence is 59,
# 26, -53, 58, 97, which sums to 187.
#
# A: Kadane's algorithm consists of a scan through the array values, computing
# at each position the maximum subarray ending at that position. This subarray
# is either empty (in which case its sum is zero) or consists of one more
# element than the maximum subarray ending at the previous position. Thus, the
# problem can be solved with the following algorithm. The algorithm keeps track
# of the tentative maximum subsequence in (maxSum, maxStartIndex, maxEndIndex).
# It accumulates a partial sum in currentMaxSum and updates the optimal range
# when this partial sum becomes larger than maxSum.


def kadane_maximum_sum_sequence(data):
   maxSum = maxStartIndex = maxEndIndex = -1
   currentMaxSum = 0
   currentStartIndex = 0
   for currentEndIndex in range(0, len(data)):
      currentMaxSum += data[currentEndIndex]
      if currentMaxSum > maxSum:
         maxSum, maxStartIndex, maxEndIndex = \
            currentMaxSum, currentStartIndex, currentEndIndex

      if currentMaxSum < 0:
         currentMaxSum = 0
         currentStartIndex = currentEndIndex + 1
   return maxSum, maxStartIndex, maxEndIndex

